home *** CD-ROM | disk | FTP | other *** search
/ Programmer Plus 2007 / Programmer-Plus-2007.iso / Programming / Report Writers / Crystal Repot 9.0 Full CD version / Setup.exe / SRC / HOARDDLL.ZIP / 3rdParty / hoard / libhoard-2.0.2 / heap.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2002-06-18  |  15.3 KB  |  406 lines
  1. ///-*-C++-*-//////////////////////////////////////////////////////////////////
  2. //
  3. // Hoard: A Fast, Scalable, and Memory-Efficient Allocator
  4. //        for Shared-Memory Multiprocessors
  5. // Contact author: Emery Berger, http://www.cs.utexas.edu/users/emery
  6. //
  7. // Copyright (c) 1998-2000, The University of Texas at Austin.
  8. //
  9. // This library is free software; you can redistribute it and/or modify
  10. // it under the terms of the GNU Library General Public License as
  11. // published by the Free Software Foundation, http://www.fsf.org.
  12. //
  13. // This library is distributed in the hope that it will be useful, but
  14. // WITHOUT ANY WARRANTY; without even the implied warranty of
  15. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16. // Library General Public License for more details.
  17. //
  18. //////////////////////////////////////////////////////////////////////////////
  19.  
  20. //////////////////////////////////////////////////////////////////////////////
  21. //
  22. // Note: This file was modified by Crystal Decisions in June 2002.
  23. //
  24. //////////////////////////////////////////////////////////////////////////////
  25.  
  26. #include "config.h"
  27.  
  28. #include "heap.h"
  29. #include "processheap.h"
  30. #include "superblock.h"
  31.  
  32. static const char version[] = "The Hoard memory allocator, version 2.0 (http://www.hoard.org). Copyright (C) 1998, 1999, 2000 The University of Texas at Austin. $Id: heap.cpp,v 1.68 2000/03/27 21:55:26 emery Exp $";
  33.  
  34. // NB: Use maketable.cpp to update this
  35. //     if SIZE_CLASSES, ALIGNMENT, SIZE_CLASS_BASE, MAX_EMPTY_SUPERBLOCKS,
  36. //     or SUPERBLOCK_SIZE changes.
  37.  
  38. #ifdef WIN32
  39. // The CRPE does a lot of 63KB buffer allocations.  So, one of the sizeclasses is modified from 56352UL to 65280UL.
  40. // The size class immediately before 64KB is 65280 (reserve 256 bytes for superblock and memory block header)
  41. size_t hoardHeap::_sizeTable[hoardHeap::SIZE_CLASSES] = {8UL, 16UL, 24UL, 32UL, 40UL, 48UL, 56UL, 72UL, 80UL, 96UL, 120UL, 144UL, 168UL, 200UL, 240UL, 288UL, 344UL, 416UL, 496UL, 592UL, 712UL, 856UL, 1024UL, 1232UL, 1472UL, 1768UL, 2120UL, 2544UL, 3048UL, 3664UL, 4392UL, 5272UL, 6320UL, 7584UL, 9104UL, 10928UL, 13112UL, 15728UL, 18872UL, 22648UL, 27176UL, 32616UL, 39136UL, 46960UL, 65280UL, 67624UL, 81144UL, 97376UL, 116848UL, 140216UL, 168256UL, 201904UL, 242288UL, 290744UL, 348896UL, 418672UL, 502408UL, 602888UL, 723464UL, 868152UL, 1041784UL, 1250136UL, 1500160UL, 1800192UL, 2160232UL, 2592280UL, 3110736UL, 3732880UL, 4479456UL, 5375344UL, 6450408UL, 7740496UL, 9288592UL, 11146312UL, 13375568UL, 16050680UL, 19260816UL, 23112984UL, 27735576UL, 33282688UL, 39939224UL, 47927072UL, 57512488UL, 69014984UL, 82817976UL, 99381576UL, 119257888UL, 143109472UL, 171731360UL, 206077632UL, 247293152UL, 296751776UL, 356102144UL, 427322560UL, 512787072UL, 615344512UL, 738413376UL, 886096064UL, 1063315264UL}; 
  42. #else
  43. size_t hoardHeap::_sizeTable[hoardHeap::SIZE_CLASSES] = {8UL, 16UL, 24UL, 32UL, 40UL, 48UL, 56UL, 72UL, 80UL, 96UL, 120UL, 144UL, 168UL, 200UL, 240UL, 288UL, 344UL, 416UL, 496UL, 592UL, 712UL, 856UL, 1024UL, 1232UL, 1472UL, 1768UL, 2120UL, 2544UL, 3048UL, 3664UL, 4392UL, 5272UL, 6320UL, 7584UL, 9104UL, 10928UL, 13112UL, 15728UL, 18872UL, 22648UL, 27176UL, 32616UL, 39136UL, 46960UL, 56352UL, 67624UL, 81144UL, 97376UL, 116848UL, 140216UL, 168256UL, 201904UL, 242288UL, 290744UL, 348896UL, 418672UL, 502408UL, 602888UL, 723464UL, 868152UL, 1041784UL, 1250136UL, 1500160UL, 1800192UL, 2160232UL, 2592280UL, 3110736UL, 3732880UL, 4479456UL, 5375344UL, 6450408UL, 7740496UL, 9288592UL, 11146312UL, 13375568UL, 16050680UL, 19260816UL, 23112984UL, 27735576UL, 33282688UL, 39939224UL, 47927072UL, 57512488UL, 69014984UL, 82817976UL, 99381576UL, 119257888UL, 143109472UL, 171731360UL, 206077632UL, 247293152UL, 296751776UL, 356102144UL, 427322560UL, 512787072UL, 615344512UL, 738413376UL, 886096064UL, 1063315264UL};
  44. #endif
  45.  
  46.  
  47. #ifndef CRYSTAL_HOARD
  48.  
  49. size_t hoardHeap::_threshold[hoardHeap::SIZE_CLASSES] = {4096UL, 2048UL, 1364UL, 1024UL, 816UL, 680UL, 584UL, 452UL, 408UL, 340UL, 272UL, 224UL, 192UL, 160UL, 136UL, 112UL, 92UL, 76UL, 64UL, 52UL, 44UL, 36UL, 32UL, 24UL, 20UL, 16UL, 12UL, 12UL, 8UL, 8UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL};
  50.  
  51. #else // CRYSTAL_HOARD
  52.  
  53. #ifdef WIN32
  54. size_t hoardHeap::_threshold[hoardHeap::SIZE_CLASSES] = {32768UL, 16384UL, 10920UL, 8192UL, 6552UL, 5460UL, 4680UL, 3640UL, 3276UL, 2728UL, 2184UL, 1820UL, 1560UL, 1308UL, 1092UL, 908UL, 760UL, 628UL, 528UL, 440UL, 368UL, 304UL, 256UL, 212UL, 176UL, 148UL, 120UL, 100UL, 84UL, 68UL, 56UL, 48UL, 40UL, 32UL, 28UL, 20UL, 16UL, 16UL, 12UL, 8UL, 8UL, 8UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL};
  55. #else
  56. size_t hoardHeap::_threshold[hoardHeap::SIZE_CLASSES] = {4096UL, 2048UL, 1364UL, 1024UL, 816UL, 680UL, 584UL, 452UL, 408UL, 340UL, 272UL, 224UL, 192UL, 160UL, 136UL, 112UL, 92UL, 76UL, 64UL, 52UL, 44UL, 36UL, 32UL, 24UL, 20UL, 16UL, 12UL, 12UL, 8UL, 8UL, 56UL, 48UL, 40UL, 32UL, 28UL, 20UL, 16UL, 16UL, 12UL, 8UL, 8UL, 8UL, 24UL, 20UL, 16UL, 12UL, 12UL, 8UL, 8UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL};
  57. #endif // WIN32
  58.  
  59. // NB:  If you change these values, you will also need to change maketable.cpp, and recalculate the
  60. // threshold table above.
  61.  
  62. // Note: I just made these numbers up.  Maybe other numbers would make more sense.
  63.  
  64. #ifdef WIN32
  65. size_t hoardHeap::_superblockSize[hoardHeap::SUPERBLOCK_CLASSES]       = { 65536UL };
  66. int hoardHeap::_reusableSuperblockLimit[hoardHeap::SUPERBLOCK_CLASSES] = { 32 };
  67. #else
  68. size_t hoardHeap::_superblockSize[hoardHeap::SUPERBLOCK_CLASSES]       = { 8192UL, 65536UL, 262144UL };
  69. int hoardHeap::_reusableSuperblockLimit[hoardHeap::SUPERBLOCK_CLASSES] = { 128, 32, 16 };
  70. #endif
  71.  
  72. #endif  // CRYSTAL_HOARD
  73.  
  74.  
  75. hoardHeap::hoardHeap (void)
  76.   : _index (0)
  77. #ifndef CRYSTAL_HOARD
  78.    ,_reusableSuperblocks (NULL),
  79.     _reusableSuperblocksCount (0)
  80. #endif
  81. #if HEAP_DEBUG
  82.   , _magic (HEAP_MAGIC)
  83. #endif
  84. {
  85.   // Initialize the per-heap lock.
  86.   hoardLockInit (_lock);
  87.   for (int i = 0; i < SUPERBLOCK_FULLNESS_GROUP; i++) {
  88.     for (int j = 0; j < SIZE_CLASSES; j++) {
  89.       // Initialize all superblocks lists to empty.
  90.       _superblocks[i][j] = NULL;
  91.     }
  92.   }
  93.   for (int k = 0; k < SIZE_CLASSES; k++) {
  94.     _leastEmptyBin[k] = 0;
  95.   }
  96. #ifdef CRYSTAL_HOARD
  97.   // Initialize the list of reusable superblocks
  98.   for ( int m = 0; m < SUPERBLOCK_CLASSES; m++)
  99.   {
  100.       _reusableSuperblocks[m] = NULL;
  101.       _reusableSuperblocksCount[m] = 0;
  102.   }
  103. #endif
  104. }
  105.  
  106.  
  107. void hoardHeap::insertSuperblock (int sizeclass,
  108.                   superblock * sb,
  109.                   processHeap * pHeap)
  110. {
  111.   assert (sb->isValid());
  112.   assert (sb->getBlockSizeClass() == sizeclass);
  113.   assert (sb->getPrev() == NULL);
  114.   assert (sb->getNext() == NULL);
  115.   assert (_magic == HEAP_MAGIC);
  116.  
  117.   // Now it's ours.
  118.   sb->setOwner (this);
  119.  
  120.   // How full is this superblock?  We'll use this information to put
  121.   // it into the right 'bin'.
  122.   sb->computeFullness();
  123.   int fullness = sb->getFullness();
  124.  
  125.   // Update the stats.
  126.   incStats (sizeclass,
  127.         sb->getNumBlocks() - sb->getNumAvailable(),
  128.         sb->getNumBlocks());
  129.  
  130.   if ((fullness == 0) &&
  131.       (sb->getNumBlocks() > 1) &&
  132.       (sb->getNumBlocks() == sb->getNumAvailable()))
  133.   {
  134.     // Recycle this superblock.
  135.     recycle (sb);
  136.   } else {
  137.  
  138.     // Insert it into the appropriate list.
  139.     superblock *& head = _superblocks[fullness][sizeclass];
  140.     sb->insertBefore (head);
  141.     head = sb;
  142.     assert (head->isValid());
  143.     
  144.     // Reset the least-empty bin counter.
  145.     _leastEmptyBin[sizeclass] = RESET_LEAST_EMPTY_BIN;
  146.   }
  147. }
  148.  
  149.  
  150. superblock * hoardHeap::removeMaxSuperblock (int sizeclass)
  151. {
  152.   assert (_magic == HEAP_MAGIC);
  153.  
  154.   superblock * head = NULL;
  155.  
  156.   // First check the reusable superblocks list.
  157.  
  158.   head = reuse (sizeclass);
  159.   if (head) {
  160.     // We found one. Since we're removing this superblock, update the
  161.     // stats accordingly.
  162.     decStats (sizeclass,
  163.           head->getNumBlocks() - head->getNumAvailable(),
  164.           head->getNumBlocks());
  165.  
  166.     return head;
  167.   }
  168.  
  169.   // Instead of finding the superblock with the most available space
  170.   // (something that would either involve a linear scan through the
  171.   // superblocks or maintaining the superblocks in sorted order), we
  172.   // just pick one that is no more than
  173.   // 1/(SUPERBLOCK_FULLNESS_GROUP-1) more full than the superblock
  174.   // with the most available space.  We start with the emptiest group.
  175.  
  176.   int i = 0;
  177.  
  178.   // Note: the last group (SUPERBLOCK_FULLNESS_GROUP - 1) is full, so
  179.   // we never need to check it. But for robustness, we leave it in.
  180.   while (i < SUPERBLOCK_FULLNESS_GROUP) {
  181.     head = _superblocks[i][sizeclass];
  182.     if (head) {
  183.       break;
  184.     }
  185.     i++;
  186.   }
  187.  
  188.   if (!head) {
  189.     return NULL;
  190.   }
  191.  
  192.   // Make sure that this superblock is at least 1/EMPTY_FRACTION
  193.   // empty.
  194.   assert (head->getNumAvailable() * EMPTY_FRACTION >= head->getNumBlocks());
  195.  
  196.   removeSuperblock (head, sizeclass);
  197.  
  198.   assert (head->isValid());
  199.   assert (head->getPrev() == NULL);
  200.   assert (head->getNext() == NULL);
  201.   return head;
  202. }
  203.  
  204.  
  205. void hoardHeap::removeSuperblock (superblock * sb,
  206.                   int sizeclass)
  207. {
  208.   assert (_magic == HEAP_MAGIC);
  209.  
  210.   assert (sb->isValid());
  211.   assert (sb->getOwner() == this);
  212.   assert (sb->getBlockSizeClass() == sizeclass);
  213.  
  214.   for (int i = 0; i < SUPERBLOCK_FULLNESS_GROUP; i++) {
  215.     if (sb == _superblocks[i][sizeclass]) {
  216.       _superblocks[i][sizeclass] = sb->getNext();
  217.       if (_superblocks[i][sizeclass] != NULL) {
  218.     assert (_superblocks[i][sizeclass]->isValid());
  219.       }
  220.       break;
  221.     }
  222.   }
  223.  
  224.   sb->remove();
  225.   decStats (sizeclass, sb->getNumBlocks() - sb->getNumAvailable(), sb->getNumBlocks());
  226. }
  227.  
  228.  
  229. void hoardHeap::moveSuperblock (superblock * sb,
  230.                 int sizeclass,
  231.                 int fromBin,
  232.                 int toBin)
  233. {
  234.   assert (_magic == HEAP_MAGIC);
  235.   assert (sb->isValid());
  236.   assert (sb->getOwner() == this);
  237.   assert (sb->getBlockSizeClass() == sizeclass);
  238.   assert (sb->getFullness() == toBin);
  239.  
  240.   // Remove the superblock from the old bin.
  241.  
  242.   superblock *& oldHead = _superblocks[fromBin][sizeclass];
  243.   if (sb == oldHead) {
  244.     oldHead = sb->getNext();
  245.     if (oldHead != NULL) {
  246.       assert (oldHead->isValid());
  247.     }
  248.   }
  249.  
  250.   sb->remove();
  251.  
  252.   // Insert the superblock into the new bin.
  253.  
  254.   superblock *& newHead = _superblocks[toBin][sizeclass];
  255.   sb->insertBefore (newHead);
  256.   newHead = sb;
  257.   assert (newHead->isValid());
  258.  
  259.   // Reset the least-empty bin counter.
  260.   _leastEmptyBin[sizeclass] = RESET_LEAST_EMPTY_BIN;
  261. }
  262.  
  263.  
  264. #ifdef CRYSTAL_HOARD
  265. bool hoardHeap::unsbrkIfLimit(processHeap * pHeap, superblock * sb)
  266. {
  267.     assert(sb!=NULL);
  268.     assert(pHeap!=NULL);
  269.     
  270.     // If we've reached our limit of reusable superblocks, then free this
  271.     // block immediately.
  272.     int sbClass = sb->getSuperblockClass();
  273.     if ( _reusableSuperblocksCount[sbClass] >= _reusableSuperblockLimit[sbClass] )
  274.     {
  275.  #if HEAP_LOG
  276.       // Record the memory deallocation.
  277.       MemoryRequest m;
  278.       m.deallocate ((int) sb->getNumBlocks() * (int) sizeFromClass(sb->getBlockSizeClass()));
  279.       pHeap->getLog(getIndex()).append(m);
  280.  #endif
  281.  #if HEAP_FRAG_STATS
  282.       pHeap->setDeallocated (0, sb->getNumBlocks() * sizeFromClass(sb->getBlockSizeClass()));
  283.  #endif
  284.       const size_t superblockSize = superblockSizeFromClass(sbClass);
  285.       hoardUnsbrk (sb, superblockSize);
  286.       return true;
  287.     }
  288.  
  289.     return false;
  290. }
  291. #endif
  292.  
  293. // The heap lock must be held when this procedure is called.
  294.  
  295. int hoardHeap::freeBlock (block *& b,
  296.                superblock *& sb,
  297.                int sizeclass,
  298.                processHeap * pHeap)
  299. {
  300.   assert (sb->isValid());
  301.   assert (b->isValid());
  302.   assert (this == sb->getOwner());
  303.  
  304.   const int oldFullness = sb->getFullness();
  305.   sb->putBlock (b);
  306.   decUStats (sizeclass);
  307.   const int newFullness = sb->getFullness();
  308.   
  309.   // Free big superblocks.
  310.   if (sb->getNumBlocks() == 1) {
  311.     removeSuperblock (sb, sizeclass);
  312.     const size_t s = sizeFromClass (sizeclass);
  313.     const int blksize = align (sizeof(block) + s);
  314. #if HEAP_LOG
  315.     // Record the memory deallocation.
  316.     MemoryRequest m;
  317.     m.deallocate ((int) sb->getNumBlocks() * (int) sizeFromClass(sb->getBlockSizeClass()));
  318.     pHeap->getLog(getIndex()).append(m);
  319. #endif
  320. #if HEAP_FRAG_STATS
  321.     pHeap->setDeallocated (0, sb->getNumBlocks() * sizeFromClass(sb->getBlockSizeClass()));
  322. #endif
  323.     hoardUnsbrk (sb, align (sizeof(superblock) + blksize));
  324.     return 1;
  325.   }
  326.  
  327.   // If the fullness value has changed, move the superblock.
  328.   if (newFullness != oldFullness) {
  329.     moveSuperblock (sb, sizeclass, oldFullness, newFullness);
  330.   } else {
  331.     // Move the superblock to the front of its list (to reduce
  332.     // paging).
  333.     superblock *& head = _superblocks[newFullness][sizeclass];
  334.     if (sb != head) {
  335.       sb->remove();
  336.       sb->insertBefore (head);
  337.       head = sb;
  338.     }
  339.   }
  340.  
  341.   // If the superblock is now empty, recycle it.
  342.  
  343.   if ((newFullness == 0) &&
  344.       (sb->getNumBlocks() == sb->getNumAvailable()))
  345.   {
  346.     removeSuperblock (sb, sizeclass);
  347. #ifdef CRYSTAL_HOARD
  348.     if (this == (hoardHeap *) pHeap) {
  349.         if (unsbrkIfLimit(pHeap,sb))
  350.             return 1;
  351.     }    
  352. #endif // CRYSTAL_HOARD
  353.     recycle (sb);
  354.     // Update the stats.  This restores the stats to their state
  355.     // before the call to removeSuperblock, above.
  356.     incStats (sizeclass,
  357.           sb->getNumBlocks() - sb->getNumAvailable(),
  358.           sb->getNumBlocks());
  359.   }
  360.  
  361.  
  362.   // If this is the process heap, then we're done.
  363.   if (this == (hoardHeap *) pHeap) {
  364.     return 0;
  365.   }
  366.  
  367.   //
  368.   // Release a superblock, if necessary.
  369.   //
  370.  
  371.   //
  372.   // Check to see if the amount free exceeds the release threshold
  373.   // (two superblocks worth of blocks for a given sizeclass) and if
  374.   // the heap is sufficiently empty.
  375.   //
  376.  
  377.   int inUse, allocated;
  378.   getStats (sizeclass, inUse, allocated);
  379.  
  380.   // printf ("inUse: %d, empty threshold: (%d; %d), allocated: %d\n", inUse, (allocated - allocated / EMPTY_FRACTION), allocated - getReleaseThreshold(sizeclass), allocated);
  381.  
  382.   if ((inUse < allocated - getReleaseThreshold(sizeclass))
  383.       && (EMPTY_FRACTION * inUse < EMPTY_FRACTION * allocated - allocated)) {
  384.     
  385.     // We've crossed the magical threshold. Find the superblock with
  386.     // the most free blocks and give it to the process heap.
  387.     superblock * const maxSb = removeMaxSuperblock (sizeclass);
  388.     assert (maxSb != NULL);
  389.  
  390.     // Update the statistics.
  391.     
  392.     assert (maxSb->getNumBlocks() >= maxSb->getNumAvailable());
  393.  
  394. #ifdef CRYSTAL_HOARD
  395.     // return 1 => don't unUpLock sb in the caller, if it was unsbrked
  396.     // inside release
  397.     if(pHeap->release (maxSb) && sb==maxSb) {
  398.       return 1;
  399.     }
  400. #else
  401.     pHeap->release (maxSb);
  402. #endif
  403.   }
  404.   return 0;
  405. }
  406.